package com.fengdi.book.hard;

public class OtherProblems {
//    public static class ReconstructQueue {
//        public int[][] reconstructQueue(int[][] people) {
//
//        }
//    }

    public static class Trap {
        public int trap(int[] height) {
            if(height.length <= 1) return 0;

            int len = height.length;
            //TODO
            // 1. 从左向右扫描整个数组，当遇到第一个正数时即为左边界，此时开始计算容量，向后继续遍历，遇到的第一个正数即为右边界，计算之间的长度即为雨水量。
            // 2. 每次循环结束后，所有高度-1，直到数组中没有正高度为止，算法结束
            int res = 0;

            while(available(height)) {
                int count = 0;
                // 找到左边界
                int left = 0;
                for(int i = 0; i < len; i++) {
                    if(height[i] > 0) {
                        left = i;
                        break;
                    }
                }

                for(int i = left; i < len; i++) {
                    if(height[i] > 0) {
                        res = res + count;
                        count = 0;
                        continue;
                    }
                    count++;
                }
                this.decreaseHeigh(height);
            }
            return res;
        }


        // 降低高度
        private void decreaseHeigh(int[] height) {
            for(int i = 0; i < height.length; i++) {
                height[i] = height[i] - 1;
            }
        }

        // 判断是否还存在正高度且数量大于等于2;
        private boolean available(int[] height) {
            int count = 0;
            for(int h : height) {
                if(h > 0) count++;
            }
            return count >= 2;
        }
    }
}
